1. Field of the Invention
The present invention relates to a system for applying sizing processing to a geometric figure, and a computer program for the same; more particularly, the invention relates to a sizing processing system wherein, when occurrence of an inside-out side is detected on an offset figure generated by applying sizing processing to a source figure, an offset figure that avoids the generation of the inside-out side is generated for the portion where the inside-out side has occurred, and a computer program for the same.
2. Description of the Related Art
With increasing integration of LSIs, CAD systems are increasingly used to design LSI circuits. In particular, for an artwork system used to produce a mask pattern when designing a circuit, geometric computation capabilities are indispensable.
One such geometric computation capability is implemented by a sizing processing method which performs processing to shrink or enlarge a mask pattern, and this method is used for such purposes as verifying setting rules for minimum spacing and minimum width of the mask pattern, detecting regions where interconnection patterns can be formed, and removing notches and protrusions. In this sizing processing, the mask pattern is taken as an input source figure, and operations are performed to translate the peripheral sides of the source figure inwardly or outwardly of the figure by a specified distance so as to obtain a shrunken or enlarged geometric figure corresponding to the source figure. Here, the shrunken figure is obtained by shrinking the source figure, and the enlarged figure by enlarging the source figure, but the figure resulting from such processing is not always a simple geometrically figure similar to the source figure.
In the sizing processing for shrinking the source image, i.e., the reduction processing, an offset figure is generated by offsetting each vertex of the source figure inwardly of the figure and translating each side accordingly. When the amount of sizing by which to translate each side is changed, the degree of shrinking of the source figure changes; for example, when the amount of sizing is small, the resulting offset figure retains a shape relatively similar to the source figure, but when the amount of sizing is large, the offset figure appears squeezed.
In the sizing processing for enlarging the source image, i.e., the enlargement processing, an offset figure is generated by offsetting each vertex of the source figure outwardly of the figure and translating each side accordingly. When the amount of sizing by which to translate each side is changed, the degree of enlargement of the source figure changes; for example, when the amount of sizing is small, the resulting offset figure retains a shape close to the source figure, but when the amount of sizing is large, the offset figure may be enlarged to such a point that the shape changes at concave vertices. Here, since a protruding portion of the source figure further protrudes as a result of the enlargement processing applied to the source figure, if the protruding portion is not needed, an edge cut operation may be inserted to cut off the protruding portion.
Shrinkage or enlargement of an LSI mask pattern is performed using such sizing processing. Various methods have been proposed for the sizing processing.
Of the proposed sizing processing methods, a first sizing processing method includes offset processing and OR processing.
In the offset processing of the first sizing processing method, the respective sides forming the source figure are translated inwardly or outwardly by a distance equal to the amount of sizing, and an offset figure is generated by sequentially connecting the offset points to which the vertices of the source figure have been moved as a result of translating the respective sides of the source figure.
In the case of reduction processing, for a concave vertex of the source figure (a convex vertex in the case of enlargement processing) the two line segments intersecting at the vertex are each translated by a distance equal to the amount of sizing, and the intersection of the extended lines of the thus translated line segments is taken as its offset point, while for a convex vertex of the source figure (a concave vertex in the case of enlargement processing) the two line segments intersecting at the vertex are each translated by a distance equal to the amount of sizing, and the end points of the thus translated line segments corresponding to the original vertex are obtained, thus generating an offset point set consisting of three points, i.e., the end points and the concave intersection point. The offset figure for the source figure is generated by sequentially connecting the points in the thus obtained offset point set.
Next, the process proceeds to the OR processing. Here, by performing an OR operation on the above offset figure, a final geometric figure is extracted as the result of the sizing processing of the source figure.
In the first sizing processing method described above, the number of offset points forming the offset figure for the source figure increases as a result of the offset processing. This is because, in the case of reduction processing, two new offset points are generated for each convex vertex. As is apparent, as the number of offset points to be generated increases, the computer takes a longer time for processing, the calculation.
In view of this, a second sizing processing method is proposed as a sizing processing method that can reduce the number of offset points to be generated in the offset processing of the source figure.
The second sizing processing method is the same as the first sizing processing method in that it includes offset processing and OR processing, but differs in the details of the offset processing, i.e., the way in which the offset points are obtained.
In the offset processing, when an offset figure made up of offset points is generated by translating the respective sides of the source figure by a distance equal to the amount of sizing, there are cases where an “inside-out side” occurs in the offset figure. Since this inside-out side is not needed in the final offset figure, the inside-out side must be removed.
The inside-out side will be described below. When the line segment joining one vertex of the source figure to the corresponding vertex of the offset figure is designated an offset line segment, there are cases where two adjacent offset line segments intersect each other. That the two adjacent offset lines intersect each other means that when one side of the source figure is offset by a distance equal to a sizing amount, this affects the slope of its adjacent side of the source figure and causes the orientation of the side of the offset figure to be reversed from the orientation of the corresponding side of the source figure. The one side of the offset figure at the ends of which these two offset line segments terminate is called the “inside-out side”. Normally, when a difference figure is obtained between the source figure and the offset figure generated as a result of the reduction processing, the difference figure should disappear, but because of the occurrence of the inside-out side, the difference figure does not disappear.
In the first sizing processing method, when the respective sides of the source figure are simply translated by a distance equal to a prescribed sizing amount, the offset point set corresponding to the source figure is generated in such a manner that for each convex vertex, three offset points including the vertex itself are generated in, for example, the case of reduction processing. In contrast, in the second sizing processing method, the offset point corresponding to one vertex is obtained as the intersection point of the two sides that are generated when the two sides of the source figure intersecting at that vertex are translated. For any other vertex of the source figure, the intersection point of the sides generated by translating the two sides intersecting at the vertex is taken as the offset point for that vertex. These points form an offset point set, and the offset figure is generated by connecting the points in the offset point set in the same order as the vertices of the source figure are arranged.
In the second sizing processing method, the number of offset points to be generated does not increase but, depending on the shape of the source figure, when two adjacent vertices are offset, the positions of the two offset points corresponding to the original vertices may be reversed from the positions of the original vertices, resulting in the inclusion of an inside-out side in a portion of the offset figure. If the OR processing is performed without removing this inside-out side, a correct result cannot be obtained. As a result, when the offset figure contains an inside-out side, the inside-out side must be removed from the offset figure.
Therefore, it is determined whether the offset figure contains an inside-out side; if an inside-out side is detected on the offset figure, the sides of the source figure associated with the inside-out side are translated by a distance equal to the prescribed sizing amount, and the intersection point of the translated sides is obtained. Then, the offset points at both ends of the inside-out side are removed from the offset point set forming the offset figure, and a new offset point set is created by adding the newly obtained intersection point in place of the removed offset points. A new offset figure is generated using the new point set. Next, the OR processing is performed on the newly generated offset figure. The OR processing is the same as that performed in the first sizing processing method.
According to the second sizing processing method, the number of offset points forming the offset figure can be greatly reduced, alleviating the computational burden in the OR processing, and even when an inside-out side occurs, the inside-out side can be easily removed.
There is also proposed a third sizing processing method that achieves faster computer processing by modifying the first sizing processing method.
In the third sizing processing method, when performing an offset operation on a convex vertex in reduction processing (concave vertex in the case of enlargement processing), if neither of the two sides of the source figure intersecting at that vertex contains an oblique line, the two sides intersecting at that vertex are respectively translated and the intersection point of the extended lines of the thus translated sides is simply taken as its offset point, rather than generating an offset point set consisting of three points associated with that vertex; on the other hand, if any one of the two sides intersecting at that vertex contains an oblique line, an offset point set consisting of three points associated with that vertex is generated.
The third sizing processing method achieves faster processing speed by adding a condition of whether an oblique line is included or not, but when such reduction processing that causes the figure to disappear is applied to the source figure, there arises the problem that, with the above added condition, a correct result cannot be obtained.
For example, consider a source figure that contains a plurality of convex vertices and one concave vertex and in which neither of the two sides intersecting at any vertex contain an oblique line, and consider the case where an offset point set is generated by applying the third reduction processing with a large sizing amount to the source figure and an offset figure is generated by sequentially connecting the offset points in the offset point set. In this case, when the OR processing is performed on the resulting offset figure, since reduction processing with such a sizing amount that causes the source figure to disappear is applied to the figure whose region has been offset, normally the figure should disappear. In actuality, however, a new region occurs in the generated offset figure. As a result, the third sizing processing method has the problem that when applying such reduction processing that causes the figure to disappear, a correct result cannot be obtained with the above added condition.
In the second sizing processing method, on the other hand, if an inside-out side occurs in the offset figure generated from a source figure containing convex vertices, the offset points associated with the inside-out side can be removed, and a new offset point can be added; as a result, the OR processing can be applied to the offset figure generated using the new offset point set.
However, when the source figure has a conspicuously protruding point, that is, when the angle between the sides of the source figure forming the protruding point is large, the offset figure can be obtained, but when the angle between the sides forming the protruding point is small, it is not easy to obtain a new offset point.
When sizing processing is applied to the source figure in accordance with the second sizing processing method, the determination of whether there is an inside-out side on the generated offset figure can be easily made by detecting an intersection point between adjacent offset locus line segments.
However, when removing the inside-out side, if the angle that the slopes of the sides of the source figure make at the protruding point is small, the offset sides generated by translating the above two sides also intersect at a small angle, and their intersection point is located far from the protruding vertex or nearly at infinity. In such cases, an overflow can occur when calculating the intersection point. If the calculation can be done in such a situation by limiting the number of significant digits, there remains the problem that a calculation error occurs.
Accordingly, it is an object of the present invention to provide a sizing processing system that can speed up offset processing without causing an overflow during calculation of an intersection point, can produce a correct result even when applying such reduction processing that deliberately causes a figure to disappear, and can easily obtain a correct sizing figure even when an edge cut is inserted in the processing of the figure.